﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using System.Diagnostics;
using System.Collections;
using System.IO;
using System.Xml;
/*
 * Project Home : http://code.google.com/p/klsudoku
 * Project Owner: ttylikl@gmail.com Email:ttylikl@qq.com
 * Project Blog : http://www.cnblogs.com/ttylikl
 * All Files of this project is free to use , but you should keep the information above when you copy&use it.
 * Infomation Modify Date: 2009.02.22
 * 
 * */
namespace SudokuPanel
{
    public class dlx_solver
    {
        const int RR = 729;
        const int CC = 324;
        const int INF = 1000000000;
        int[] mem = new int[RR + 9];
        int[] ans = new int[RR + 9];
        char[] ch = new char[RR + 9];
        int[] cnt = new int[CC + 9];
        class node
        {
            public int r, c;
            public node up;
            public node down;
            public node left;
            public node right;
        };
        node head;
        node[] all = new node[RR * CC + 99];
        node[] row = new node[RR];
        node[] col = new node[CC];
        int all_t;
        void link(int r, int c)
        {
            cnt[c]++;
            node t = all[all_t];
            if (t == null)
            {
                t = new node();
                all[all_t] = t;
            }
            all_t++;
            t.r = r;
            t.c = c;
            t.left = row[r];
            t.right = row[r].right;
            t.left.right = t;
            t.right.left = t;
            t.up = col[c];
            t.down = col[c].down;
            t.up.down = t;
            t.down.up = t;
        }
        void remove(int c)
        {
            node t, tt;
            col[c].right.left = col[c].left;
            col[c].left.right = col[c].right;
            for (t = col[c].down; !Object.ReferenceEquals(t, col[c]); t = t.down)
            {
                for (tt = t.right; !Object.ReferenceEquals(tt, t); tt = tt.right)
                {
                    cnt[tt.c]--;
                    tt.up.down = tt.down;
                    tt.down.up = tt.up;
                }
                t.left.right = t.right;
                t.right.left = t.left;
            }
        }
        void resume(int c)
        {
            node t, tt;
            for (t = col[c].down; !Object.ReferenceEquals(t, col[c]); t = t.down)
            {
                t.right.left = t;
                t.left.right = t;
                for (tt = t.left; !Object.ReferenceEquals(tt, t); tt = tt.left)
                {
                    cnt[tt.c]++;
                    tt.down.up = tt;
                    tt.up.down = tt;
                }
            }
            col[c].left.right = col[c];
            col[c].right.left = col[c];
        }
        int solve(int k)
        {
            if (Object.ReferenceEquals(head.right, head))
                return 1;
            node t, tt;
            int min = INF, tc=0;
            for (t = head.right; !Object.ReferenceEquals(t, head); t = t.right)
            {
                if (cnt[t.c] < min)
                {
                    min = cnt[t.c];
                    tc = t.c;
                    if (min <= 1) break;
                }
            }
            remove(tc);
            int scnt = 0;
            for (t = col[tc].down; !Object.ReferenceEquals(t, col[tc]); t = t.down)
            {
                if (mem[k] != 0)
                    Debug.Write("");
                mem[k] = t.r;
                t.left.right = t;
                for (tt = t.right; !Object.ReferenceEquals(tt, t); tt = tt.right)
                {
                    remove(tt.c);
                }
                t.left.right = t.right;
                scnt += solve(k + 1);
                if (!chk_unique && scnt ==1)
                    return scnt;
                if (scnt > 1)
                    return scnt;
                //继续找下一个可能
                t.right.left = t;
                for (tt = t.left; !Object.ReferenceEquals(tt, t); tt = tt.left)
                {
                    resume(tt.c);
                }
                t.right.left = t.left;
            }

            resume(tc);
            return scnt;
        }

        private bool chk_unique = false;
        public int scount=0;
        public int solution_count(String str)
        {
            chk_unique=true;
            run(str);
            return scount;
        }
        public String do_solve(String str)
        {
            chk_unique = false;
            String ret=run(str);
            if (scount != 1)
                return "";
            return ret;
        }
        private String run(String str)
        {
            mem = new int[RR + 9];
            ans = new int[RR + 9];
            ch = new char[RR + 9];

            //Debug.WriteLine("dlx_solve(" + str + ")");
            String s=str.Replace("\r","");
            s=s.Replace("\n","");
            ch = s.ToCharArray();

            cnt = new int[CC + 9];
            head = new node();
            all = new node[RR * CC + 99];
            row = new node[RR];
            col = new node[CC];
            /*while(gets(ch))*/
            {
                int i;
                //if(ch[0]=='e')break;
                all_t = 1;
                cnt = new int[CC + 9];
                head.left = head;
                head.right = head;
                head.up = head;
                head.down = head;
                head.r = RR;
                head.c = CC;
                for (i = 0; i < CC; i++)
                {
                    col[i] = new node();
                    col[i].c = i;
                    col[i].r = RR;
                    col[i].up = col[i];
                    col[i].down = col[i];
                    col[i].left = head;
                    col[i].right = head.right;
                    col[i].left.right = col[i];
                    col[i].right.left = col[i];
                }
                for (i = 0; i < RR; i++)
                {
                    row[i] = new node();
                    row[i].r = i;
                    row[i].c = CC;
                    row[i].left = row[i];
                    row[i].right = row[i];
                    row[i].up = head;
                    row[i].down = head.down;
                    row[i].up.down = row[i];
                    row[i].down.up = row[i];
                }
                for (i = 0; i < RR; i++)
                {
                    int r = i / 9 / 9 % 9;
                    int c = i / 9 % 9;
                    int val = i % 9 + 1;
                    if (ch[r * 9 + c] == '.' || ch[r * 9 + c] == '0' || ch[r * 9 + c] == val + '0')
                    {
                        link(i, r * 9 + val - 1);
                        link(i, 81 + c * 9 + val - 1);
                        int tr = r / 3;
                        int tc = c / 3;
                        link(i, 162 + (tr * 3 + tc) * 9 + val - 1);
                        link(i, 243 + r * 9 + c);
                    }
                }
                for (i = 0; i < RR; i++)
                {
                    row[i].left.right = row[i].right;
                    row[i].right.left = row[i].left;
                }
                scount = solve(1);
                for (i = 1; i <= 81; i++)
                {
                    int t = mem[i] / 9 % 81;
                    int val = mem[i] % 9 + 1;
                    //Debug.WriteLine("t=" + t.ToString("00")+ "mem[" + i.ToString("D2")+ "]="+mem[i]+" val=" + val + "i=" + i.ToString("D2"));
                    ans[t] = val;
                }
                StringBuilder sb = new StringBuilder();
                for (i = 0; i < 81; i++)
                {
                    //Debug.Write(ans[i]);
                    //if (ans[i] == 0)
                    //    Debug.Write("val=0!");
                    sb.Append(ans[i]);
                }
                //Debug.WriteLine("");
                //Debug.WriteLine("scnt=" + solution_count);
                return sb.ToString();
            }
        }
    }
}